package Tree;

public class _236_LowestCommonAncestorofaBinaryTree {
    TreeNode lowestNode = null;
    public TreeNode lowestCommonAncestor_1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if (isDescendant(root, p.val) && isDescendant(root, q.val)) {
            lowestNode = root;
        }
        lowestCommonAncestor_1(root.left, p, q);
        lowestCommonAncestor_1(root.right, p, q);
        return lowestNode;
    }

    public boolean isDescendant(TreeNode root, int val) {
        if(root==null) return false;
        return root.val==val || isDescendant(root.left, val) || isDescendant(root.right, val);
    }

    //reference solution:
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q) return root;
        TreeNode lnode = lowestCommonAncestor(root.left, p, q);
        TreeNode rnode = lowestCommonAncestor(root.right, p, q);
        if (lnode != null && rnode != null) {
            return root;
        } else {
            return lnode != null ? lnode : rnode;
        }
    }
}
